{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Merge Similar Items"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #hash-table #ordered-set #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #哈希表 #有序集合 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: mergeSimilarItems"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #合并相似的物品"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你两个二维整数数组&nbsp;<code>items1</code> 和&nbsp;<code>items2</code>&nbsp;，表示两个物品集合。每个数组&nbsp;<code>items</code>&nbsp;有以下特质：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>items[i] = [value<sub>i</sub>, weight<sub>i</sub>]</code> 其中&nbsp;<code>value<sub>i</sub></code>&nbsp;表示第&nbsp;<code>i</code>&nbsp;件物品的&nbsp;<strong>价值</strong>&nbsp;，<code>weight<sub>i</sub></code>&nbsp;表示第 <code>i</code>&nbsp;件物品的 <strong>重量</strong>&nbsp;。</li>\n",
    "\t<li><code>items</code>&nbsp;中每件物品的价值都是 <strong>唯一的</strong>&nbsp;。</li>\n",
    "</ul>\n",
    "\n",
    "<p>请你返回一个二维数组&nbsp;<code>ret</code>，其中&nbsp;<code>ret[i] = [value<sub>i</sub>, weight<sub>i</sub>]</code>，&nbsp;<code>weight<sub>i</sub></code>&nbsp;是所有价值为&nbsp;<code>value<sub>i</sub></code><sub>&nbsp;</sub>物品的&nbsp;<strong>重量之和</strong>&nbsp;。</p>\n",
    "\n",
    "<p><strong>注意：</strong><code>ret</code>&nbsp;应该按价值 <strong>升序</strong>&nbsp;排序后返回。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>items1 = [[1,1],[4,5],[3,8]], items2 = [[3,1],[1,5]]\n",
    "<b>输出：</b>[[1,6],[3,9],[4,5]]\n",
    "<b>解释：</b>\n",
    "value = 1 的物品在 items1 中 weight = 1 ，在 items2 中 weight = 5 ，总重量为 1 + 5 = 6 。\n",
    "value = 3 的物品再 items1 中 weight = 8 ，在 items2 中 weight = 1 ，总重量为 8 + 1 = 9 。\n",
    "value = 4 的物品在 items1 中 weight = 5 ，总重量为 5 。\n",
    "所以，我们返回 [[1,6],[3,9],[4,5]] 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>items1 = [[1,1],[3,2],[2,3]], items2 = [[2,1],[3,2],[1,3]]\n",
    "<b>输出：</b>[[1,4],[2,4],[3,4]]\n",
    "<b>解释：</b>\n",
    "value = 1 的物品在 items1 中 weight = 1 ，在 items2 中 weight = 3 ，总重量为 1 + 3 = 4 。\n",
    "value = 2 的物品在 items1 中 weight = 3 ，在 items2 中 weight = 1 ，总重量为 3 + 1 = 4 。\n",
    "value = 3 的物品在 items1 中 weight = 2 ，在 items2 中 weight = 2 ，总重量为 2 + 2 = 4 。\n",
    "所以，我们返回 [[1,4],[2,4],[3,4]] 。</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>items1 = [[1,3],[2,2]], items2 = [[7,1],[2,2],[1,4]]\n",
    "<b>输出：</b>[[1,7],[2,4],[7,1]]\n",
    "<strong>解释：\n",
    "</strong>value = 1 的物品在 items1 中 weight = 3 ，在 items2 中 weight = 4 ，总重量为 3 + 4 = 7 。\n",
    "value = 2 的物品在 items1 中 weight = 2 ，在 items2 中 weight = 2 ，总重量为 2 + 2 = 4 。\n",
    "value = 7 的物品在 items2 中 weight = 1 ，总重量为 1 。\n",
    "所以，我们返回 [[1,7],[2,4],[7,1]] 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= items1.length, items2.length &lt;= 1000</code></li>\n",
    "\t<li><code>items1[i].length == items2[i].length == 2</code></li>\n",
    "\t<li><code>1 &lt;= value<sub>i</sub>, weight<sub>i</sub> &lt;= 1000</code></li>\n",
    "\t<li><code>items1</code>&nbsp;中每个 <code>value<sub>i</sub></code>&nbsp;都是 <b>唯一的</b>&nbsp;。</li>\n",
    "\t<li><code>items2</code>&nbsp;中每个 <code>value<sub>i</sub></code>&nbsp;都是 <b>唯一的</b>&nbsp;。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [merge-similar-items](https://leetcode.cn/problems/merge-similar-items/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [merge-similar-items](https://leetcode.cn/problems/merge-similar-items/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[1,1],[4,5],[3,8]]\\n[[3,1],[1,5]]', '[[1,1],[3,2],[2,3]]\\n[[2,1],[3,2],[1,3]]', '[[1,3],[2,2]]\\n[[7,1],[2,2],[1,4]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mergeSimilarItems(self, items1: List[List[int]], items2: List[List[int]]) -> List[List[int]]:\n",
    "        cnt = Counter()\n",
    "        for v, w in chain(items1, items2):\n",
    "            cnt[v] += w\n",
    "        return sorted(cnt.items())\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mergeSimilarItems(self, items1: List[List[int]], items2: List[List[int]]) -> List[List[int]]:\n",
    "        def getFirst(elem):\n",
    "            return elem[0]\n",
    "        items = items1 + items2\n",
    "        items.sort(key = getFirst)\n",
    "        ans = [[items[0][0],items[0][1]]]\n",
    "        for i in range(1,len(items)):\n",
    "            if items[i][0] == ans[len(ans)-1][0]:\n",
    "                ans[len(ans)-1][1] = ans[len(ans)-1][1] + items[i][1]\n",
    "            else:\n",
    "                ans.append(items[i])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mergeSimilarItems(self, items1: List[List[int]], items2: List[List[int]]) -> List[List[int]]:\n",
    "        fpr = Counter()\n",
    "        for v in items1:\n",
    "            fpr[v[0]] += v[1]\n",
    "        for p in items2:\n",
    "            fpr[p[0]] += p[1]\n",
    "        fpr = sorted(fpr.items())\n",
    "        return fpr\n",
    "        \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mergeSimilarItems(self, items1: List[List[int]], items2: List[List[int]]) -> List[List[int]]:\n",
    "        hashMap = { value : weight for value, weight in items1 }\n",
    "        for value, weight in items2:\n",
    "            if value in hashMap:\n",
    "                hashMap[value] += weight\n",
    "            else:\n",
    "                hashMap[value] = weight\n",
    "        \n",
    "        return sorted([ (value, hashMap[value]) for value in hashMap.keys() ])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mergeSimilarItems(self, items1: List[List[int]], items2: List[List[int]]) -> List[List[int]]:\n",
    "        map={}\n",
    "        for a,b in items1:\n",
    "            map[a]=b\n",
    "        for a,b in items2:\n",
    "            if a in map:\n",
    "                map[a] += b\n",
    "            else:\n",
    "                map[a] = b\n",
    "        return sorted([a,b] for a,b in map.items())\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mergeSimilarItems(self, items1: List[List[int]], items2: List[List[int]]) -> List[List[int]]:\n",
    "        hash = {v: w for v, w in items1}\n",
    "        for v, w in items2:\n",
    "            hash[v] = hash.get(v, 0) + w\n",
    "        return sorted(list(hash.items()))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mergeSimilarItems(self, items1: List[List[int]], items2: List[List[int]]) -> List[List[int]]:\n",
    "        temp={}\n",
    "        for tt in items1:\n",
    "            temp[tt[0]]=tt[1]\n",
    "        for tt in items2:\n",
    "            if temp.get(tt[0]):\n",
    "                temp[tt[0]]+=tt[1]\n",
    "            else:\n",
    "                temp[tt[0]]=tt[1]\n",
    "        res=sorted(temp.items(),key=lambda x:x[0])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mergeSimilarItems(self, items1: List[List[int]], items2: List[List[int]]) -> List[List[int]]:\n",
    "        items1 += items2\n",
    "        items1.sort()\n",
    "        r = [[items1[0][0], items1[0][1]]]\n",
    "        for i in range(1, len(items1)):\n",
    "            if items1[i][0] == items1[i-1][0]:\n",
    "                r[-1][1] += items1[i][1]\n",
    "            else:\n",
    "                r.append(items1[i])\n",
    "        return r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mergeSimilarItems(self, items1: List[List[int]], items2: List[List[int]]) -> List[List[int]]:\n",
    "        map = Counter()\n",
    "        for a, b in items1:\n",
    "            map[a] += b\n",
    "        for a, b in items2:\n",
    "            map[a] += b\n",
    "        return sorted([a, b] for a, b in map.items())\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mergeSimilarItems(self, items1: List[List[int]], items2: List[List[int]]) -> List[List[int]]:\n",
    "        items3 = items2 + items1\n",
    "        d = {}\n",
    "        for k, v in items3:\n",
    "            if d.get(k):\n",
    "                d[k] += v\n",
    "            else:\n",
    "                d[k] = v\n",
    "        return sorted([a, b] for a, b in d.items())\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mergeSimilarItems(self, items1: List[List[int]], items2: List[List[int]]) -> List[List[int]]:\n",
    "        item_weight = collections.defaultdict(int)\n",
    "\n",
    "        for item in items1:\n",
    "            item_weight[item[0]] += item[1]\n",
    "        for item in items2:\n",
    "            item_weight[item[0]] += item[1]\n",
    "        result = [[key, item_weight[key]] for key in item_weight]\n",
    "        return sorted(result, key=lambda x: x[0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def mergeSimilarItems(self, items1: List[List[int]], items2: List[List[int]]) -> List[List[int]]:\n",
    "        items1.sort()\n",
    "        items2.sort()\n",
    "        ret = []\n",
    "        i = 0\n",
    "        j = 0\n",
    "        while i < len(items1) and j < len(items2):\n",
    "            if items1[i][0] == items2[j][0]:\n",
    "                ret.append([items1[i][0], items1[i][1] + items2[j][1]])\n",
    "                i += 1\n",
    "                j += 1\n",
    "            elif items1[i][0] > items2[j][0]:\n",
    "                ret.append([items2[j][0], items2[j][1]])\n",
    "                j += 1\n",
    "            else:\n",
    "                ret.append([items1[i][0], items1[i][1]])\n",
    "                i += 1\n",
    "        if i < len(items1):\n",
    "            ret += items1[i:]\n",
    "        if j < len(items2):\n",
    "            ret += items2[j:]\n",
    "        return ret\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mergeSimilarItems(self, items1: List[List[int]], items2: List[List[int]]) -> List[List[int]]:\n",
    "        # items1=dict(items1)\n",
    "        # items2=dict(items2)\n",
    "        # for (i,j) in items2.items():\n",
    "        #     if i not in items1.keys():\n",
    "        #         items1.setdefault(i,j)\n",
    "        #     else:\n",
    "        #         items1[i]+=j\n",
    "        # return sorted(list(items1.items()))\n",
    "        map=Counter()\n",
    "        for a,b in items1:\n",
    "            map[a]+=b\n",
    "        for a,b in items2:\n",
    "            map[a]+=b\n",
    "        return sorted(list(map.items()))\n",
    "\n",
    "        \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mergeSimilarItems(self, items1: List[List[int]], items2: List[List[int]]) -> List[List[int]]:\n",
    "        hashmap = {}\n",
    "        for item in items1:\n",
    "            hashmap[item[0]] = item[1]\n",
    "        for item in items2:\n",
    "            if item[0] in hashmap:\n",
    "                hashmap[item[0]]+=item[1]\n",
    "            else:\n",
    "                hashmap[item[0]] = item[1]\n",
    "        \n",
    "        res = []\n",
    "        for key in sorted(hashmap.keys()):\n",
    "            res.append([key, hashmap[key]])\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def mergeSimilarItems(self, items1, items2):\n",
    "        items1.sort()\n",
    "        items2.sort()\n",
    "        ans=[]\n",
    "        n1,n2=len(items1),len(items2)\n",
    "        i,j=0,0\n",
    "        while i<n1 and j<n2:\n",
    "            if items1[i][0]==items2[j][0]:\n",
    "                item=[items1[i][0],items1[i][1]+items2[j][1]]\n",
    "                ans.append(item)\n",
    "                i+=1\n",
    "                j+=1\n",
    "            elif items1[i][0]>items2[j][0]:\n",
    "                ans.append(items2[j])\n",
    "                j+=1\n",
    "            else:\n",
    "                ans.append(items1[i])\n",
    "                i+=1\n",
    "        if i==n1:\n",
    "            # n2>n1\n",
    "            ans.extend(items2[j:])\n",
    "\n",
    "        elif j==n2:\n",
    "            # n1>n2\n",
    "            ans.extend(items1[i:])\n",
    "        ans.sort()\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mergeSimilarItems(self, items1: List[List[int]], items2: List[List[int]]) -> List[List[int]]:\n",
    "        r = defaultdict(int)\n",
    "        for v, w in chain(items1, items2):\n",
    "            r[v] += w\n",
    "        return sorted([k, v] for k, v in r.items())\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mergeSimilarItems(self, items1: List[List[int]], items2: List[List[int]]) -> List[List[int]]:\n",
    "        res = []\n",
    "        hash_d = {}\n",
    "        items1.extend(items2)\n",
    "        for l in items1:\n",
    "            hash_d[l[0]] = hash_d.get(l[0],0) + l[1]\n",
    "        return sorted([[k,v] for k,v in hash_d.items()])\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mergeSimilarItems(self, items1: List[List[int]], items2: List[List[int]]) -> List[List[int]]:\n",
    "        map=Counter()\n",
    "        for a,b in items1:\n",
    "            map[a]+=b\n",
    "        \n",
    "        for a,b in items2:\n",
    "            map[a]+=b\n",
    "        \n",
    "        return sorted([a,b] for a,b in map.items())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mergeSimilarItems(self, items1: List[List[int]], items2: List[List[int]]) -> List[List[int]]:\n",
    "        total = items1 + items2\n",
    "        n = len(total)\n",
    "        total.sort()\n",
    "        weight = total[0][1]\n",
    "        ret =[]\n",
    "        for i in range(1,n):\n",
    "            if total[i][0] == total[i-1][0]:\n",
    "                weight =weight +total[i][1]\n",
    "            else:\n",
    "                ret.append([total[i-1][0],weight])\n",
    "                weight = total[i][1]\n",
    "        ret.append([total[-1][0],weight])\n",
    "        ret.sort()\n",
    "        return ret\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mergeSimilarItems(self, items1: List[List[int]], items2: List[List[int]]) -> List[List[int]]:\n",
    "        cnt = Counter()\n",
    "        for v, w in chain(items1, items2):\n",
    "            cnt[v] += w\n",
    "        return sorted(cnt.items())\n",
    "\n",
    "\n",
    "           \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mergeSimilarItems(self, items1: List[List[int]], items2: List[List[int]]) -> List[List[int]]:\n",
    "        map = Counter()\n",
    "        for a, b in items1:\n",
    "            map[a] += b\n",
    "        for a, b in items2:\n",
    "            map[a] += b\n",
    "        return sorted([a, b] for a, b in map.items())\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mergeSimilarItems(self, items1: List[List[int]], items2: List[List[int]]) -> List[List[int]]:\n",
    "        cnt = Counter()\n",
    "        for v, w in chain(items1, items2):\n",
    "            cnt[v] += w\n",
    "        # return [[v, cnt[v]] for v in range(1, 1001) if cnt[v]]\n",
    "        return sorted(cnt.items())\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mergeSimilarItems(self, items1: List[List[int]], items2: List[List[int]]) -> List[List[int]]:\n",
    "        items1.extend(items2)\n",
    "        items1.sort()\n",
    "        res=[items1[0]]\n",
    "        for i in range(1,len(items1)):\n",
    "            if res[-1][0]==items1[i][0]:\n",
    "                res[-1][1]+=items1[i][1]\n",
    "            else:\n",
    "                res.append(items1[i])\n",
    "        res.sort()\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mergeSimilarItems(self, items1: List[List[int]], items2: List[List[int]]) -> List[List[int]]:\n",
    "        map = Counter()\n",
    "        for a, b in items1:\n",
    "            map[a] += b\n",
    "        for a, b in items2:\n",
    "            map[a] += b\n",
    "        return sorted([a, b] for a, b in map.items())\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mergeSimilarItems(self, items1: List[List[int]], items2: List[List[int]]) -> List[List[int]]:\n",
    "        map = Counter()\n",
    "        for v, w in items1:\n",
    "            map[v] += w\n",
    "        for v, w in items2:\n",
    "            map[v] += w\n",
    "        return sorted([v, w] for v, w in map.items())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mergeSimilarItems(self, items1: List[List[int]], items2: List[List[int]]) -> List[List[int]]:\n",
    "        map=collections.Counter()\n",
    "        for a,b in items1:\n",
    "            map[a]+=b\n",
    "        for a,b in items2:\n",
    "            map[a]+=b\n",
    "        return sorted([a,b] for a,b in map.items())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mergeSimilarItems(self, items1: List[List[int]], items2: List[List[int]]) -> List[List[int]]:\n",
    "        map = Counter()\n",
    "        for a, b in items1:\n",
    "            map[a] += b\n",
    "        for a, b in items2:    \n",
    "            map[a] += b\n",
    "        return sorted([a, b] for a, b in map.items())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mergeSimilarItems(self, items1: List[List[int]], items2: List[List[int]]) -> List[List[int]]:\n",
    "        res = []\n",
    "        hash_d = {}\n",
    "        items1.extend(items2)\n",
    "        for l in items1:\n",
    "            hash_d[l[0]] = hash_d.get(l[0],0) + l[1]\n",
    "        return sorted([[k,v] for k,v in hash_d.items()])\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mergeSimilarItems(self, items1: List[List[int]], items2: List[List[int]]) -> List[List[int]]:\n",
    "        _dict = {}\n",
    "        for item in items1 + items2:\n",
    "            if item[0] not in _dict:\n",
    "                _dict[item[0]] = item[1]\n",
    "            else:\n",
    "                _dict[item[0]] += item[1]\n",
    "\n",
    "        _list = []\n",
    "        for k,v in _dict.items():\n",
    "            _list.append([k,v])\n",
    "\n",
    "        _list.sort(key=lambda x: x[0])\n",
    "\n",
    "        return _list"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mergeSimilarItems(self, items1: List[List[int]], items2: List[List[int]]) -> List[List[int]]:\n",
    "        sum_=items1+items2\n",
    "        value=[]\n",
    "        sum_.sort()\n",
    "        for i in sum_:\n",
    "            value.append(i[0])\n",
    "        # print(value)\n",
    "        values=list(set(value))\n",
    "        values.sort()\n",
    "        ans=[]\n",
    "        for j in values:\n",
    "            mid=[]\n",
    "            for z in sum_:\n",
    "                if j==z[0]:\n",
    "                    mid.append(z[1])\n",
    "            # print(mid)\n",
    "            # print(sum(mid))\n",
    "            ans.append([j,sum(mid)])\n",
    "            # print(ans)\n",
    "        return ans \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mergeSimilarItems(self, items1: List[List[int]], items2: List[List[int]]) -> List[List[int]]:\n",
    "        dic  = {}\n",
    "        for i in items1:\n",
    "            if i[0] in dic:\n",
    "                dic[i[0]] += i[1]\n",
    "            else:\n",
    "                dic[i[0]] = i[1]\n",
    "        \n",
    "        for i in items2:\n",
    "            if i[0] in dic:\n",
    "                dic[i[0]] += i[1]\n",
    "            else:\n",
    "                dic[i[0]] = i[1]\n",
    "        ans = []\n",
    "        for i in dic:\n",
    "            ans.append([i,dic[i]])\n",
    "        ans.sort()\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mergeSimilarItems(self, items1: List[List[int]], items2: List[List[int]]) -> List[List[int]]:\n",
    "        a={}\n",
    "        for i in items1:\n",
    "            if i[0] not in a:\n",
    "                a[i[0]]=i[1]\n",
    "            else:\n",
    "                a[i[0]]+=i[1]\n",
    "        for i in items2:\n",
    "            if i[0] not in a:\n",
    "                a[i[0]]=i[1]\n",
    "            else:\n",
    "            \ta[i[0]]+=i[1]\n",
    "        ret=[]\n",
    "        for i in a:\n",
    "            ret.append([i,a[i]])\n",
    "        ret.sort(key=lambda a:a[0])\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mergeSimilarItems(self, items1: List[List[int]], items2: List[List[int]]) -> List[List[int]]:\n",
    "        a = len(items1)\n",
    "        b = len(items2)\n",
    "        if a < b:\n",
    "            items1, items2 = items2, items1\n",
    "        for i in range(len(items2)):\n",
    "            n = 0\n",
    "            for j in range(len(items1)):\n",
    "                if items1[j][0] == items2[i][0]:\n",
    "                    items1[j][1] = items1[j][1] + items2[i][1]\n",
    "                else:\n",
    "                    n += 1\n",
    "            if n == len(items1):\n",
    "                items1.append(items2[i])\n",
    "        items1.sort(key=lambda x: x[0])\n",
    "        return items1\n",
    "                     "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mergeSimilarItems(self, items1: List[List[int]], items2: List[List[int]]) -> List[List[int]]:\n",
    "        mp = {}\n",
    "        for item in items1:\n",
    "            mp[item[0]] = mp.get(item[0], 0) + item[1]\n",
    "\n",
    "        for item in items2:\n",
    "            mp[item[0]] = mp.get(item[0], 0) + item[1]\n",
    "        \n",
    "        ans = []\n",
    "        for item in mp.items():\n",
    "            ans.append(item)\n",
    "        \n",
    "        ans.sort()\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mergeSimilarItems(self, items1: List[List[int]], items2: List[List[int]]) -> List[List[int]]:\n",
    "        counter = dict()\n",
    "        for v , w in items1 :\n",
    "            if counter.get(v) is None :\n",
    "                counter[v] = w \n",
    "            else :\n",
    "                counter[v] += w \n",
    "        for v , w in items2 :\n",
    "            if counter.get(v) is None :\n",
    "                counter[v] = w \n",
    "            else :\n",
    "                counter[v] += w \n",
    "        return sorted(list(counter.items()))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mergeSimilarItems(self, items1: List[List[int]], items2: List[List[int]]) -> List[List[int]]:\n",
    "        dic = {}\n",
    "        for k, v in items2 + items1:\n",
    "            if k in dic:\n",
    "                dic[k] += v\n",
    "            else:\n",
    "                dic[k] = v\n",
    "        return sorted([[k, v] for k, v in dic.items()])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mergeSimilarItems(self, items1: List[List[int]], items2: List[List[int]]) -> List[List[int]]:\n",
    "        dic = {k: v for k, v in items1}\n",
    "        for k, v in items2:\n",
    "            if k in dic:\n",
    "                dic[k] += v\n",
    "            else:\n",
    "                dic[k] = v\n",
    "        return sorted([[k, v] for k, v in dic.items()])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mergeSimilarItems(self, items1: List[List[int]], items2: List[List[int]]) -> List[List[int]]:\n",
    "        d = defaultdict(int)\n",
    "        for v, w in items1:\n",
    "            d[v] += w\n",
    "        for v, w in items2:\n",
    "            d[v] += w\n",
    "        ans = [[i, d[i]] for i in sorted(d.keys())]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mergeSimilarItems(self, items1, items2):\n",
    "        merged_items = {}\n",
    "        \n",
    "        for item in items1 + items2:\n",
    "            value, weight = item\n",
    "            if value in merged_items:\n",
    "                merged_items[value] += weight\n",
    "            else:\n",
    "                merged_items[value] = weight\n",
    "        \n",
    "        ret = [[value, weight] for value, weight in merged_items.items()]\n",
    "        ret.sort(key=lambda x: x[0])\n",
    "        \n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mergeSimilarItems(self, items1: List[List[int]], items2: List[List[int]]) -> List[List[int]]:\n",
    "        res=Counter()\n",
    "        for i in items1+items2:\n",
    "            res[i[0]]+=i[1]\n",
    "        \n",
    "        return sorted([a,b] for a,b in res.items())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mergeSimilarItems(self, items1: List[List[int]], items2: List[List[int]]) -> List[List[int]]:\n",
    "        map = Counter()\n",
    "        for a, b in items1:\n",
    "            map[a] += b\n",
    "        for a, b in items2:\n",
    "            map[a] += b\n",
    "        return sorted([a, b] for a, b in map.items())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mergeSimilarItems(self, items1: List[List[int]], items2: List[List[int]]) -> List[List[int]]:\n",
    "        if len(items1) < len(items2):\n",
    "            items1, items2 = items2, items1\n",
    "        ls1 = dict(items1)\n",
    "        for n in range(len(items2)):\n",
    "            if items2[n][0] in ls1:\n",
    "                ls1[items2[n][0]] = ls1.get(items2[n][0]) + items2[n][1]\n",
    "            else:\n",
    "                ls1[items2[n][0]] = items2[n][1]\n",
    "        del items2\n",
    "        ls = list(ls1.items())\n",
    "        ls.sort(key=lambda x: x[0])\n",
    "        return ls\n",
    "                     "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mergeSimilarItems(self, items1: List[List[int]], items2: List[List[int]]) -> List[List[int]]:\n",
    "        dic = {}\n",
    "        for i in items1:\n",
    "            dic[i[0]] = i[1]\n",
    "        for i in items2:\n",
    "            try:\n",
    "                dic[i[0]] += i[1]\n",
    "            except:\n",
    "                dic[i[0]] = i[1]\n",
    "        ans = []\n",
    "        for key in dic:\n",
    "            ans.append([key, dic[key]])\n",
    "        ans.sort()\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mergeSimilarItems(self, items1: List[List[int]], items2: List[List[int]]) -> List[List[int]]:\n",
    "        d = {}\n",
    "        for item in items1:\n",
    "            k, v = item\n",
    "            if k in d:\n",
    "                d[k] += v\n",
    "            else:\n",
    "                d[k] = v\n",
    "        for item in items2:\n",
    "            k, v = item\n",
    "            if k in d:\n",
    "                d[k] += v\n",
    "            else:\n",
    "                d[k] = v\n",
    "        ans = [[k, v] for k, v in d.items()]\n",
    "        ans.sort(key=lambda x: x[0])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mergeSimilarItems(self, items1: List[List[int]], items2: List[List[int]]) -> List[List[int]]:\n",
    "        items = items1 + items2\n",
    "        d = {}\n",
    "        for x, y in items:\n",
    "            d[x] = d.get(x, 0) + y\n",
    "        return sorted(d.items())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mergeSimilarItems(self, items1: List[List[int]], items2: List[List[int]]) -> List[List[int]]:\n",
    "        map = Counter()\n",
    "        for a, b in items1:\n",
    "            map[a] += b\n",
    "        for a, b in items2:\n",
    "            map[a] += b\n",
    "        return sorted([a, b] for a, b in map.items())\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mergeSimilarItems(self, items1: List[List[int]], items2: List[List[int]]) -> List[List[int]]:\n",
    "        d = collections.defaultdict(int)\n",
    "        for x, y in items1:\n",
    "            d[x] += y\n",
    "        for x, y in items2:\n",
    "            d[x] += y\n",
    "\n",
    "        res = list(d.items())\n",
    "        # print(d)\n",
    "        res.sort()\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mergeSimilarItems(self, items1: List[List[int]], items2: List[List[int]]) -> List[List[int]]:\n",
    "        if len(items1) < len(items2):\n",
    "            items1, items2 = items2, items1\n",
    "        ls1 = dict(items1)\n",
    "        del items1\n",
    "        for n in range(len(items2)):\n",
    "            if items2[n][0] in ls1:\n",
    "                ls1[items2[n][0]] = ls1.get(items2[n][0]) + items2[n][1]\n",
    "            else:\n",
    "                ls1[items2[n][0]] = items2[n][1]\n",
    "        del items2\n",
    "        ls = list(ls1.items())\n",
    "        ls.sort(key=lambda x: x[0])\n",
    "        return ls\n",
    "                     "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mergeSimilarItems(self, items1: List[List[int]], items2: List[List[int]]) -> List[List[int]]:\n",
    "        hax = dict(items1)\n",
    "        for i in items2:\n",
    "            if i[0] not in hax:\n",
    "                hax[i[0]] = i[1]\n",
    "            else:\n",
    "                hax[i[0]] += i[1]\n",
    "        ret = []\n",
    "        for i in sorted(hax):\n",
    "            ret.append([i, hax[i]])\n",
    "        return ret\n",
    "        \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mergeSimilarItems(self, items1: List[List[int]], items2: List[List[int]]) -> List[List[int]]:\n",
    "        dict1={}\n",
    "        dict2={}\n",
    "\n",
    "        for a in items1:\n",
    "            dict1[a[0]]=a[1]\n",
    "        \n",
    "        for b in items2:\n",
    "            dict2[b[0]]=b[1]\n",
    "        \n",
    "        for temp in dict1.keys():\n",
    "            if temp in dict2.keys():\n",
    "                dict2[temp]+=dict1[temp]\n",
    "            else:\n",
    "                dict2[temp] = dict1[temp]\n",
    "        l_sort=[]\n",
    "        for i in dict2.keys():\n",
    "            l_sort.append(i)\n",
    "        l_sort.sort()\n",
    "        result=[]\n",
    "        for j in l_sort:\n",
    "            result.append([j,dict2[j]])\n",
    "\n",
    "        print(result)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mergeSimilarItems(self, items1: List[List[int]], items2: List[List[int]]) -> List[List[int]]:\n",
    "        items1=Counter({i[0]:i[1] for i in items1})\n",
    "        items2=Counter({i[0]:i[1] for i in items2})\n",
    "        res=[[key,value] for key,value in dict(items1+items2).items()]\n",
    "        res.sort(key=lambda x:x[0])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mergeSimilarItems(self, items1: List[List[int]], items2: List[List[int]]) -> List[List[int]]:\n",
    "        res = []\n",
    "        hash_d = {}\n",
    "        items1.extend(items2)\n",
    "        for l in items1:\n",
    "            hash_d[l[0]] = hash_d.get(l[0],0) + l[1]\n",
    "        return sorted([[k,v] for k,v in hash_d.items()])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "\n",
    "class Solution:\n",
    "    def mergeSimilarItems(self, items1: List[List[int]], items2: List[List[int]]) -> List[List[int]]:\n",
    "        ds1,ds2 = Counter(),Counter()\n",
    "        for x in items1:\n",
    "            ds1[x[0]] = x[1]\n",
    "        for x in items2:\n",
    "            ds2[x[0]] = x[1]\n",
    "        return sorted([[k,v] for k,v in (ds1 + ds2).items()],key = lambda x:x[0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mergeSimilarItems(self, items1: List[List[int]], items2: List[List[int]]) -> List[List[int]]:\n",
    "        res = []\n",
    "        hash_d = {}\n",
    "        items1.extend(items2)\n",
    "        for l in items1:\n",
    "            hash_d[l[0]] = hash_d.get(l[0],0) + l[1]\n",
    "        return sorted([[k,v] for k,v in hash_d.items()])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mergeSimilarItems(self, items1: List[List[int]], items2: List[List[int]]) -> List[List[int]]:\n",
    "        cnt=collections.defaultdict(int)\n",
    "        for val,wei in items1:\n",
    "            cnt[val]+=wei\n",
    "        for val,wei in items2:\n",
    "            cnt[val]+=wei\n",
    "        res=[]\n",
    "        # print(cnt)\n",
    "        for val,wei in cnt.items():\n",
    "            # print(val)\n",
    "            res.append([val,wei])\n",
    "        # print(res)\n",
    "        res.sort(key=lambda x:x[0])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mergeSimilarItems(self, items1: List[List[int]], items2: List[List[int]]) -> List[List[int]]:\n",
    "        cnt = Counter(dict(items1))\n",
    "        cnt += dict(items2)\n",
    "        return sorted(cnt.items())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mergeSimilarItems(self, items1: List[List[int]], items2: List[List[int]]) -> List[List[int]]:\n",
    "        map = Counter()\n",
    "        for a, b in items1:\n",
    "            map[a] += b\n",
    "        for a, b in items2:\n",
    "            map[a] += b\n",
    "        return sorted([a, b] for a, b in map.items())\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mergeSimilarItems(self, items1: List[List[int]], items2: List[List[int]]) -> List[List[int]]:\n",
    "        map = Counter()\n",
    "        for a, b in items1:\n",
    "            map[a] += b\n",
    "        for a, b in items2:\n",
    "            map[a] += b\n",
    "        return sorted([a, b] for a, b in map.items())\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mergeSimilarItems(self, items1: List[List[int]], items2: List[List[int]]) -> List[List[int]]:\n",
    "        items1.sort(key = lambda x:x[0])\n",
    "        items2.sort(key = lambda x:x[0])\n",
    "\n",
    "        ret = Counter()\n",
    "        for a,b in items1:\n",
    "            ret[a] += b\n",
    "        for a,b in items2:\n",
    "            ret[a] += b\n",
    "\n",
    "        return sorted([v,w] for v,w in ret.items())\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "\n",
    "class Solution:\n",
    "    def mergeSimilarItems(self, items1: List[List[int]], items2: List[List[int]]) -> List[List[int]]:\n",
    "        ds1,ds2 = Counter(),Counter()\n",
    "        for x in items1:\n",
    "            ds1[x[0]] = x[1]\n",
    "        for x in items2:\n",
    "            ds2[x[0]] = x[1]\n",
    "        return sorted([[k,v] for k,v in (ds1 + ds2).items()],key = lambda x:x[0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mergeSimilarItems(self, items1: List[List[int]], items2: List[List[int]]) -> List[List[int]]:\n",
    "        map = collections.Counter()\n",
    "        for a,b in items1:\n",
    "            map[a] += b\n",
    "        for a,b in items2:\n",
    "            map[a] += b\n",
    "        return sorted([a,b] for a,b in map.items())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mergeSimilarItems(self, items1: List[List[int]], items2: List[List[int]]) -> List[List[int]]:\n",
    "        item = []\n",
    "        for i in range(len(items1)):\n",
    "            item.append(items1[i][0])\n",
    "        for i in range(len(items2)):\n",
    "            item.append(items2[i][0])\n",
    "        item = list(set(item))\n",
    "        weight = [0] * len(item)\n",
    "        for i in range(len(items1)):\n",
    "            weight[item.index(items1[i][0])] += items1[i][1]\n",
    "        for i in range(len(items2)):\n",
    "            weight[item.index(items2[i][0])] += items2[i][1]\n",
    "        res = []\n",
    "        for i in range(len(item)):\n",
    "            res.append([item[i], weight[i]])\n",
    "        res = sorted(res, key = lambda x:x[0], reverse = False)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mergeSimilarItems(self, items1: List[List[int]], items2: List[List[int]]) -> List[List[int]]:\n",
    "        r = defaultdict(int)\n",
    "        for value, weight in chain(items1, items2):\n",
    "            r[value] += weight\n",
    "        return sorted([k, v] for k, v in r.items())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mergeSimilarItems(self, items1: List[List[int]], items2: List[List[int]]) -> List[List[int]]:\n",
    "        m,n,res=len(items1),len(items2),[]\n",
    "        mp=dict()\n",
    "        for i in range(m):\n",
    "            mp[items1[i][0]]=items1[i][1]\n",
    "        for i in range(n):\n",
    "            if mp.get(items2[i][0],0)!=0:\n",
    "                mp[items2[i][0]]+=items2[i][1]\n",
    "            else:\n",
    "                mp[items2[i][0]]=items2[i][1]\n",
    "        for key,value in mp.items():\n",
    "            res.append([key,value])\n",
    "        res.sort(key=lambda x:x[0])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mergeSimilarItems(self, items1: List[List[int]], items2: List[List[int]]) -> List[List[int]]:\n",
    "        res={}\n",
    "        for i in items1+items2:\n",
    "            if i[0] in res:\n",
    "                res[i[0]]+=i[1]\n",
    "            else:\n",
    "                res[i[0]]=i[1]\n",
    "        res=sorted(res.items(),key=lambda x:x[0])\n",
    "        print(res)\n",
    "        return [list(i) for i in res]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mergeSimilarItems(self, items1: List[List[int]], items2: List[List[int]]) -> List[List[int]]:\n",
    "        items3 = items2 + items1\n",
    "        res = []\n",
    "\n",
    "        counter = dict(Counter(map(lambda x: x[0], items3)))\n",
    "\n",
    "        for key in counter.keys():\n",
    "            s = sum(map(lambda x: x[1], filter(lambda x: x[0] == key, items3)))\n",
    "            res.append([key, s])\n",
    "            \n",
    "        res.sort(key=lambda x: x[0])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mergeSimilarItems(self, items1: List[List[int]], items2: List[List[int]]) -> List[List[int]]:\n",
    "        a = dict(items1)\n",
    "        for i in items2:\n",
    "            if i[0] in a:\n",
    "                a[i[0]] += i[1]\n",
    "            else:\n",
    "                a[i[0]] = i[1]\n",
    "        b = [[i, a[i] ] for i in a]\n",
    "        return sorted(b, key=lambda x: x[0])\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mergeSimilarItems(self, items1: List[List[int]], items2: List[List[int]]) -> List[List[int]]:\n",
    "        items1=dict(items1)\n",
    "        items2=dict(items2)\n",
    "        for (i,j) in items2.items():\n",
    "            if i not in items1.keys():\n",
    "                items1.setdefault(i,j)\n",
    "            else:\n",
    "                items1[i]+=j\n",
    "        return sorted(list(items1.items()))\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mergeSimilarItems(self, items1: List[List[int]], items2: List[List[int]]) -> List[List[int]]:\n",
    "        m = {}\n",
    "        for v,w in items1:\n",
    "            m[v] = w\n",
    "        for v,w in items2:\n",
    "            if v in m:\n",
    "                m[v] += w\n",
    "            else:\n",
    "                m[v] = w\n",
    "        ans = []\n",
    "        for v,w in m.items():\n",
    "            ans.append([v,w])\n",
    "        return sorted(ans,key = lambda x: x[0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mergeSimilarItems(self, items1: List[List[int]], items2: List[List[int]]) -> List[List[int]]:\n",
    "        items = items1 + items2\n",
    "        values = list(set([x[0] for x in items]))\n",
    "        values.sort()\n",
    "        ret = [[val, 0] for val in values]\n",
    "        for item in items:\n",
    "            for idx, x in enumerate(ret):\n",
    "                if item[0] == x[0]:\n",
    "                    ret[idx][1] += item[1]\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mergeSimilarItems(self, items1: List[List[int]], items2: List[List[int]]) -> List[List[int]]:\n",
    "        if len(items1) < len(items2):\n",
    "            items1, items2 = items2, items1\n",
    "        ls1 = dict(items1)\n",
    "        del items1\n",
    "        for n in range(len(items2)):\n",
    "            if items2[n][0] in ls1:\n",
    "                ls1[items2[n][0]] = ls1.get(items2[n][0]) + items2[n][1]\n",
    "            else:\n",
    "                ls1[items2[n][0]] = items2[n][1]\n",
    "        del items2\n",
    "        ls = list(ls1.items())\n",
    "        ls.sort(key=lambda x: x[0])\n",
    "        return ls\n",
    "                     "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mergeSimilarItems(self, items1: List[List[int]], items2: List[List[int]]) -> List[List[int]]:\n",
    "        items1.sort(key=lambda x: x[0])\n",
    "        items2.sort(key=lambda x: x[0])\n",
    "        ret = []\n",
    "        left = 0\n",
    "        right = 0\n",
    "        while left < len(items1) or right < len(items2):\n",
    "            if left < len(items1):\n",
    "                num1 = items1[left]\n",
    "            else:\n",
    "                num1 = [inf, inf]\n",
    "            if right < len(items2):           \n",
    "                num2 = items2[right]\n",
    "            else:\n",
    "                num2 = [inf, inf]\n",
    "            if num1[0] == num2[0]:\n",
    "                ret.append([num1[0], num1[1]+num2[1]])\n",
    "                left += 1\n",
    "                right += 1\n",
    "            elif num1[0] < num2[0]:\n",
    "                ret.append([num1[0], num1[1]])\n",
    "                left += 1\n",
    "            else:\n",
    "                ret.append([num2[0], num2[1]])\n",
    "                right += 1\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mergeSimilarItems(self, items1: List[List[int]], items2: List[List[int]]) -> List[List[int]]:\n",
    "        d = {}\n",
    "        for items in items1:\n",
    "            k = items[0]\n",
    "            v = items[1]\n",
    "            if k in d:\n",
    "                d[k] += v\n",
    "            else:\n",
    "                d[k] = v\n",
    "        \n",
    "        for items in items2:\n",
    "            k = items[0]\n",
    "            v = items[1]\n",
    "            if k in d:\n",
    "                d[k] += v\n",
    "            else:\n",
    "                d[k] = v\n",
    "        \n",
    "        d1 = dict(sorted(d.items(), key=lambda x: x[0]))\n",
    "\n",
    "        final_items = []\n",
    "        for k,v in d1.items():\n",
    "            final_items.append([k, v])\n",
    "        \n",
    "\n",
    "\n",
    "        return final_items\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mergeSimilarItems(self, items1: List[List[int]], items2: List[List[int]]) -> List[List[int]]:\n",
    "        # ans = dict()\n",
    "        # for value, weight in items1:\n",
    "        #     ans[value] = weight\n",
    "        ans = {value: weight for value, weight in items1}\n",
    "        for value, weight in items2:\n",
    "            if value not in ans:\n",
    "                ans[value] = weight\n",
    "            else:\n",
    "                ans[value] += weight\n",
    "        ret = []\n",
    "        for value,weight in ans.items():\n",
    "            ret.append([value, weight])\n",
    "        ret.sort(key=lambda x:x[0])\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 哈希表，一行写法，将items作为键值对传入dict，然后通过Counter把值加起来\n",
    "class Solution:\n",
    "    def mergeSimilarItems(self, items1: List[List[int]], items2: List[List[int]]) -> List[List[int]]:\n",
    "\n",
    "        return sorted((Counter(dict(items1)) + Counter(dict(items2))).items())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mergeSimilarItems(self, items1: List[List[int]], items2: List[List[int]]) -> List[List[int]]:\n",
    "        cnt = defaultdict(int)\n",
    "        for x, y in items1:\n",
    "            cnt[x] += y\n",
    "        for x, y in items2:\n",
    "            cnt[x] += y\n",
    "        res = []\n",
    "        tmp = sorted(cnt.items(), key=lambda x:x[0])\n",
    "        for t in tmp:\n",
    "            res.append(list(t))\n",
    "        return res"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
